{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary of common problems with *Link List*\n",
    "\n",
    "[简体中文JavaScript版](https://mp.weixin.qq.com/s/ZtF0fkQa8wZGXmeRDIvHtg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *Idle Time*\n",
    "\n",
    "The *Daily Problem* channel has been updated continuously for 60 days. Subscribers know that the quality of the topic is very high. I will do it every day, in order not to waste money to buy this topic every day.\n",
    "\n",
    "Yep, I paid for these questions. Although most of them are available on [*LeetCode*][1], I still feel it's more suitable for you and me after selection and daily distribution. \n",
    "\n",
    "For 60 days, some people have been following me, such as [*@Dragon1573*][2]. He recorded every question and answer I pushed on [*Github*][3] and merged it by week. Post a picture and everyone feels.\n",
    "\n",
    "![Repository Snapshot](images/Link_List-1.jpg)\n",
    "\n",
    "The URL address of the repository is **<https://github.com/Dragon1573/Daily-Problem>**\n",
    "\n",
    "[1]: https://leetcode.com/\n",
    "[2]: https://github.com/Dragon1573\n",
    "[3]: https://github.com/\n",
    "\n",
    "****"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Revision Time\n",
    "\n",
    "Today I won't push any questions. I'll sort out the basics of the linked list to ensure that everyone is addicted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x0 Summary\n",
    "\n",
    "1. *Linked list* usually is a string of *Node*, which a *Node* contains a value `val` and a pointer `next` referring the next node.\n",
    "2. Most of the time, we should use multiple pointers to solve the question.\n",
    "3. When the head node of the linked list is insure, use a fake head node `dummyHead`.\n",
    "4. Master the *reverse list*!\n",
    "5. **Skills:** In order to judge the *circular list*, let a pointer moves twice as fast as the other.\n",
    "6. A *doubly linked list*, that is, a linked list with 2 pointers. One of them pointing to the next and the other pointing to the previous.\n",
    "\n",
    "Here, we prepared 5 questions for everyone. We recommended you can write it down by hand if you have free time.\n",
    "\n",
    "- Reverse the linked list\n",
    "- Remove the recommended element in the linked list\n",
    "- Generate an odd-even linked list\n",
    "- Check a palindrome linked list\n",
    "- Realize a doubly linked list on your own"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x1 Define a Node structure\n",
    "\n",
    "Apart from *JavaScript*, *Python 3* is an object-oriented programming language. In order to express the algorithm accurately, we have to define a *Node* first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    ''' Node Definition '''\n",
    "    \n",
    "    def __init__(self, value, next_=None):\n",
    "        ''' The Constructor '''\n",
    "        self.value = value\n",
    "        self.next_ = next_\n",
    "    \n",
    "    def __str__(self):\n",
    "        ''' Linked List Stringify '''\n",
    "        string = str(self.value)\n",
    "        self = self.next_\n",
    "        while self is not None:\n",
    "            string += ('->' + str(self.value))\n",
    "            self = self.next_\n",
    "        return string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x2 Reverse a linked list\n",
    "\n",
    "In this part, we provide both iterably and recursively algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ReverseLinkedList:\n",
    "    ''' Reverse a linked list '''\n",
    "    \n",
    "    def iterably(self, array: Node):\n",
    "        ''' Reverse iterably '''\n",
    "        previous = None\n",
    "        current = array\n",
    "        while current is not None:\n",
    "            next_ = current.next_\n",
    "            current.next_ = previous\n",
    "            previous = current\n",
    "            current = next_\n",
    "        return previous\n",
    "    \n",
    "    def recursively(self, array: Node):\n",
    "        ''' Reverse recursively '''\n",
    "        if array is None:\n",
    "            return None\n",
    "        if array.next_ is None:\n",
    "            return array\n",
    "        previous = self.recursively(array.next_)\n",
    "        array.next_.next_ = array\n",
    "        array.next_ = None\n",
    "        return previous\n",
    "    \n",
    "    def test(self):\n",
    "        ''' Test cases '''\n",
    "        array = Node(1, Node(2, Node(3, Node(4, Node(5)))))\n",
    "        print(array)\n",
    "        reversed_result = self.iterably(array)\n",
    "        print(reversed_result)\n",
    "        reverse_again = self.recursively(reversed_result)\n",
    "        print(reverse_again)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5\n",
      "5->4->3->2->1\n",
      "1->2->3->4->5\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "ReverseLinkedList().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x3 Revome Element(s) in a linked list\n",
    "\n",
    "```text\n",
    "Input: 1->2->6->3->4->5->6\n",
    "Output: 1->2->3->4->5\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RemoveElement:\n",
    "    ''' Remove all elements with recommended value in a linked list '''\n",
    "    \n",
    "    def remove(self, array: Node, value):\n",
    "        ''' Remove element '''\n",
    "        dummy = Node(0, array)\n",
    "        cursor = dummy\n",
    "        while cursor is not None and cursor.next_ is not None:\n",
    "            if cursor.next_.value == value:\n",
    "                next_ = cursor.next_.next_\n",
    "                cursor.next_.next_ = None\n",
    "                cursor.next_ = next_\n",
    "            cursor = cursor.next_\n",
    "        return dummy.next_\n",
    "    \n",
    "    def test(self):\n",
    "        ''' Test Cases '''\n",
    "        array = Node(1, Node(2, Node(6, Node(3, Node(4, Node(5, Node(6)))))))\n",
    "        print(array)\n",
    "        result = self.remove(array, 6)\n",
    "        print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->6->3->4->5->6\n",
      "1->2->3->4->5\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "RemoveElement().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x4 Generate an odd-even linked list\n",
    "\n",
    "Link all odd and even index nodes together seprately, then connect even linked list after the odd one. Return a new linked list.\n",
    "\n",
    "```text\n",
    "Input: 1->2->3->4->5\n",
    "Output: 1->3->5->2->4\n",
    "```\n",
    "\n",
    "```text\n",
    "Input: 2->1->3->5->6->4->7\n",
    "Output: 2->3->6->7->1->5->4\n",
    "```\n",
    "\n",
    "**Notes:** *The first element is odd and the second element is even, etc..*\n",
    "\n",
    "You should finish it with $O(1)$ space complexity and $O(n)$ time complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OddEvenList:\n",
    "    ''' Generate an odd-even linked list '''\n",
    "    \n",
    "    def group(self, array: Node):\n",
    "        ''' Group odd and even together '''\n",
    "        if array is None:\n",
    "            return array\n",
    "        odd = array\n",
    "        even = array.next_\n",
    "        even_head = even\n",
    "        while odd.next_ is not None and even.next_ is not None:\n",
    "            odd.next_ = even.next_\n",
    "            odd = odd.next_\n",
    "            even.next_ = odd.next_\n",
    "            even = even.next_\n",
    "        odd.next_ = even_head\n",
    "        return array\n",
    "    \n",
    "    def test(self):\n",
    "        ''' Test Cases '''\n",
    "        array_1 = Node(1, Node(2, Node(3, Node(4, Node(5)))))\n",
    "        print(array_1)\n",
    "        grouped_1 = self.group(array_1)\n",
    "        print(grouped_1)\n",
    "        array_2 = Node(2, Node(1, Node(3, Node(5, Node(6, Node(4, Node(7)))))))\n",
    "        print(array_2)\n",
    "        grouped_2 = self.group(array_2)\n",
    "        print(grouped_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5\n",
      "1->3->5->2->4\n",
      "2->1->3->5->6->4->7\n",
      "2->3->6->7->1->5->4\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "OddEvenList().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x5 Check a palindrome linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PalindromeLinkedList:\n",
    "    ''' Palindrome linked list '''\n",
    "    \n",
    "    def reverse(self, array: Node):\n",
    "        ''' Reverse a linked list '''\n",
    "        previous = None\n",
    "        current = array\n",
    "        while current is not None:\n",
    "            next_ = current.next_\n",
    "            current.next_ = previous\n",
    "            previous = current\n",
    "            current = next_\n",
    "        return previous\n",
    "    \n",
    "    def isPalindrome(self, array: Node):\n",
    "        ''' Check if it is a palindrome '''\n",
    "        reversed_list = self.reverse(array)\n",
    "        while array is not None:\n",
    "            if array.value != reversed_list.value:\n",
    "                return False\n",
    "            array = array.next_\n",
    "            reversed_list = reversed_list.next_\n",
    "        return True\n",
    "    \n",
    "    def test(self):\n",
    "        ''' Test Cases '''\n",
    "        print(self.isPalindrome(Node(1, Node(2))))\n",
    "        print(self.isPalindrome(Node(1, Node(2, Node(2, Node(1))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "PalindromeLinkedList().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x6 Realize a doubly linked list on your own\n",
    "\n",
    "Such as `get()`, `addHead()`, `addTail()`, `deleteAtIndex()` and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoublyNode:\n",
    "    ''' Doubly Node '''\n",
    "    \n",
    "    def __init__(self, value, next_=None, prev=None):\n",
    "        ''' The Constructor '''\n",
    "        self.value = value\n",
    "        self.next_ = next_\n",
    "        self.prev = prev\n",
    "        \n",
    "    def __str__(self):\n",
    "        ''' Stringify a list '''\n",
    "        string = str(self.value)\n",
    "        self = self.next_\n",
    "        while self:\n",
    "            string += ('<->' + str(self.value))\n",
    "        return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoublyLinkedList:\n",
    "    ''' Doubly linked list '''\n",
    "    \n",
    "    def __init__(self):\n",
    "        ''' The Constructor '''\n",
    "        self.head = Node(None)\n",
    "        self.tail = Node(None)\n",
    "        self.head.next_ = self.tail\n",
    "        self.tail.prev = self.head\n",
    "    \n",
    "    def getNode(self, index):\n",
    "        ''' Get a node from an index '''\n",
    "        current = self.head.next_\n",
    "        while current and index > 0:\n",
    "            current = current.next_\n",
    "            index -= 1\n",
    "        if current == self.tail or not current or index != 0:\n",
    "            return None\n",
    "        return current\n",
    "    \n",
    "    def get(self, index):\n",
    "        ''' Get the value of the index '''\n",
    "        node = self.getNode(index)\n",
    "        if node:\n",
    "            return node.value\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    def addHead(self, value):\n",
    "        ''' Add an element at the begin of the list '''\n",
    "        node = Node(value)\n",
    "        node.prev = self.head\n",
    "        node.next_ = self.head.next_\n",
    "        self.head.next_.prev = node\n",
    "        self.head.next_ = node\n",
    "    \n",
    "    def addTail(self, value):\n",
    "        ''' Add an element at the end of the list '''\n",
    "        node = Node(value)\n",
    "        node.prev = self.tail.prev\n",
    "        node.next_ = self.tail\n",
    "        self.tail.prev.next_ = node\n",
    "        self.tail.prev = node\n",
    "    \n",
    "    def addAtIndex(self, index, value):\n",
    "        ''' Add an element at an index '''\n",
    "        current = self.getNode(index)\n",
    "        if current is None:\n",
    "            raise IndexError('Index out of bounds!')\n",
    "        node = Node(value)\n",
    "        node.prev = current.prev\n",
    "        node.next_ = current\n",
    "        current.prev.next_ = node\n",
    "        current.prev = node\n",
    "    \n",
    "    def deleteAtIndex(self, index):\n",
    "        ''' Remove the element at the index '''\n",
    "        current = self.getNode(index)\n",
    "        if current is None:\n",
    "            raise IndexError('Index out of bounds!')\n",
    "        current.prev.next_ = current.next_\n",
    "        current.next_.prev = current.prev\n",
    "        current.next_ = None\n",
    "        current.prev = None\n",
    "    \n",
    "    def test(self):\n",
    "        ''' Test Cases '''\n",
    "        self.addHead(0)\n",
    "        self.addTail(5)\n",
    "        print(self.head)\n",
    "        self.addAtIndex(1, 1)\n",
    "        self.addAtIndex(2, 2)\n",
    "        print(self.head)\n",
    "        self.addAtIndex(3, 3)\n",
    "        self.addAtIndex(4, 4)\n",
    "        print(self.head)\n",
    "        self.deleteAtIndex(0)\n",
    "        print(self.head)\n",
    "        self.deleteAtIndex(4)\n",
    "        print(self.head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None->0->5->None\n",
      "None->0->1->2->5->None\n",
      "None->0->1->2->3->4->5->None\n",
      "None->1->2->3->4->5->None\n",
      "None->1->2->3->4->None\n"
     ]
    }
   ],
   "source": [
    "''' Main Scripts '''\n",
    "DoublyLinkedList().test()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
